/*
 * String.h
 *
 *  Created on: Jan 23, 2013
 *      Author: Lucifer
 */

#ifndef __BFX_STRING_H__
#define __BFX_STRING_H__

#include "StringTraits.h"

namespace BFX
{

//////////////////////////////////////////////////////////////////////////////

template<typename T, class StrTraits = StringTraitsT<T> >
class BFX_TMPL StringT
{
	typedef T XCHAR;
	typedef T* PXSTR;
	typedef const T* PCXSTR;

private:
	struct StringData: public REFObject
	{
		StringData(int nCapacity = 0) :
				m_pBuffer(NULL), m_nLength(0), m_nAllocLength(0)
		{
			if (nCapacity > 0)
			{
				Capacity(nCapacity);
			}
		}
		virtual ~StringData()
		{
			if (m_pBuffer != NULL)
				delete[] m_pBuffer;
		}
		bool IsShared() const
		{
			return (GetRefCount() > 1);
		}
		void Capacity(int nCapacity)
		{
			BFX_ASSERT(nCapacity >= 0);

			// calculate required buffer length, align by m_nAllocLength.
			int nAllocSize = __MAX(m_nAllocLength + 1, 16);
			while (nAllocSize < (nCapacity + 1)) // end with '\0'
			{
				nAllocSize *= 2;
			}
			// if overflow then allocate new.
			if (nAllocSize > (m_nAllocLength + 1))
			{
				XCHAR* pNewBuffer = new XCHAR[nAllocSize];
				if (m_nLength > 0)
					memcpy(pNewBuffer, m_pBuffer, m_nLength * sizeof(XCHAR));

				if (m_pBuffer != NULL)
					delete[] m_pBuffer;

				m_pBuffer = pNewBuffer;
				m_nAllocLength = (nAllocSize - 1);
			}
		}
		PXSTR m_pBuffer;
		int m_nLength;
		int m_nAllocLength;
	};
public:
	StringT() :
			m_pData(new StringData())
	{
	}
	StringT(PCXSTR pchSrc, int nLength = -1)
	{
		BFX_REQUIRE(pchSrc != NULL || nLength == 0);
		if (nLength == -1)
		{
			nLength = StrTraits::StringLength(pchSrc);
		}

		BFX_ENSURE(nLength >= 0);
		m_pData = new StringData(nLength);
		if (nLength > 0)
		{
			memcpy(m_pData->m_pBuffer, pchSrc, nLength * sizeof(XCHAR));
			SetLength(nLength);
		}
	}
	StringT(XCHAR ch, int nLength = 1)
	{
		BFX_REQUIRE(nLength >= 0);
		m_pData = new StringData(nLength);
		if (nLength > 0)
		{
			memset(m_pData->m_pBuffer, ch, nLength * sizeof(XCHAR));
			SetLength(nLength);
		}
	}
	StringT(const StringT& strSrc) :
			m_pData(strSrc.m_pData)
	{
	}
	virtual ~StringT()
	{
	}

	operator PCXSTR() const
	{
		return GetData();
	}
	StringT& operator=(const StringT& strSrc)
	{
		m_pData = strSrc.m_pData;
		return (*this);
	}

	XCHAR operator[](int iChar) const
	{
		BFX_REQUIRE(iChar >= 0 && iChar < GetLength());

		return GetData()[iChar];
	}

	int GetLength() const
	{
		return (m_pData->m_nLength);
	}
	PCXSTR GetData() const
	{
		return (m_pData->m_pBuffer);
	}
	bool IsEmpty() const
	{
		return (GetLength() == 0);
	}
	void SetEmpty()
	{
		if (IsEmpty())
			return;
		if (!m_pData->IsShared())
			// Don't reallocate a locked buffer that's shrinking
			SetLength(0);
		else
			m_pData = new StringData();
	}

	void Append(XCHAR ch)
	{
		int nNewLength = GetLength() + 1;
		PXSTR pszBuffer = GetBuffer(nNewLength);
		pszBuffer[GetLength()] = ch;
		SetLength(nNewLength);
	}
	void Append(PCXSTR pszSrc)
	{
		Append(pszSrc, StrTraits::StringLength(pszSrc));
	}
	void Append(PCXSTR pszSrc, int nLength)
	{
		// See comment in SetString() about why we do this
		UINT32 nOffset = pszSrc - GetData();

		UINT32 nOldLength = GetLength();
		if (nOldLength < 0)
		{
			// protects from underflow
			nOldLength = 0;
		}

		// Make sure the nLength is greater than zero
		BFX_ENSURE(nLength >= 0);

		//Make sure we don't read pass end of the terminating NULL
		BFX_ASSERT(StrTraits::StringLength(pszSrc) >= nLength);

		int nNewLength = nOldLength + nLength;
		PXSTR pszBuffer = GetBuffer(nNewLength);
		if (nOffset <= nOldLength)
		{
			pszSrc = pszBuffer + nOffset;
		}
		memcpy(pszBuffer + nOldLength, pszSrc, nLength * sizeof(XCHAR));
		SetLength(nNewLength);
	}

	StringT Insert(int iIndex, XCHAR ch) const
	{
		BFX_REQUIRE(iIndex >= 0);

		StringT strResult(*this);
		BFX_REQUIRE(iIndex < strResult.GetLength());

		int nNewLength = strResult.GetLength() + 1;
		PXSTR pszBuffer = strResult.GetBuffer(nNewLength);
		// move existing bytes down
		memmove(pszBuffer + iIndex + 1, pszBuffer + iIndex, (nNewLength - iIndex) * sizeof(XCHAR));
		pszBuffer[iIndex] = ch;

		strResult.SetLength(nNewLength);

		return (strResult);
	}
	StringT Insert(int iIndex, PCXSTR psz) const
	{
		BFX_REQUIRE(iIndex >= 0);

		StringT strResult(*this);
		BFX_REQUIRE(iIndex < strResult.GetLength());

		// nInsertLength and nNewLength are in XCHARs
		int nInsertLength = StrTraits::StringLength(psz);
		int nNewLength = strResult.GetLength();
		if (nInsertLength > 0)
		{
			nNewLength += nInsertLength;

			PXSTR pszBuffer = strResult.GetBuffer(nNewLength);
			// move existing bytes down
			memmove(pszBuffer + iIndex + nInsertLength, pszBuffer + iIndex,
					(nNewLength - iIndex - nInsertLength + 1) * sizeof(XCHAR));
			memcpy(pszBuffer + iIndex, psz, nInsertLength * sizeof(XCHAR));
			strResult.SetLength(nNewLength);
		}

		return (strResult);
	}
	StringT Remove(int iIndex, int nCount = 1) const
	{
		BFX_REQUIRE(iIndex >= 0);
		BFX_REQUIRE(nCount >= 0);

		StringT strResult(*this);
		int nLength = GetLength();
		BFX_REQUIRE((iIndex + nCount) <= nLength);

		if (nCount > 0)
		{
			int nNewLength = nLength - nCount;
			int nCharsToCopy = nLength - (iIndex + nCount) + 1;
			PXSTR pszBuffer = strResult.GetBuffer();
			memmove(pszBuffer + iIndex, pszBuffer + iIndex + nCount, nCharsToCopy * sizeof(XCHAR));
			strResult.SetLength(nNewLength);
		}

		return (strResult);
	}
	StringT Replace(XCHAR chOld, XCHAR chNew) const
	{
		StringT strResult(*this);

		// short-circuit the nop case
		if (chOld != chNew)
		{
			// otherwise modify each character that matches in the string
			PXSTR pszBuffer = strResult.GetBuffer();
			int nLength = strResult.GetLength();
			for (int iChar = 0; iChar < nLength; iChar++)
			{
				// replace instances of the specified character only
				if (pszBuffer[iChar] == chOld)
				{
					pszBuffer[iChar] = chNew;
				}
			}
			strResult.SetLength(nLength);
		}
		return (strResult);
	}
	StringT Replace(PCXSTR pszOld, PCXSTR pszNew) const
	{
		// can't have empty or NULL lpszOld
		// nSourceLen is in XCHARs
		int nSourceLen = StrTraits::StringLength(pszOld);
		BFX_ENSURE(nSourceLen > 0);

		// nReplacementLen is in XCHARs
		int nReplacementLen = StrTraits::StringLength(pszNew);

		// loop once to figure out the size of the result string
		StringT<XCHAR> strResult(*this);
		int nCount = 0;
		PCXSTR pszStart = strResult.GetBuffer();
		PCXSTR pszEnd = pszStart + GetLength();
		while (pszStart < pszEnd)
		{
			PCXSTR pszTarget;
			while ((pszTarget = StrTraits::StringScanSet(pszStart, pszOld)) != NULL)
			{
				nCount++;
				pszStart = pszTarget + nSourceLen;
			}
			pszStart += StrTraits::StringLength(pszStart) + 1;
		}

		// if any changes were made, make them
		if (nCount > 0)
		{
			// if the buffer is too small, just allocate a new buffer (slow but sure)
			int nOldLength = strResult.GetLength();
			int nNewLength = nOldLength + (nReplacementLen - nSourceLen) * nCount;

			PXSTR pszBuffer = strResult.GetBuffer(__MAX(nNewLength, nOldLength));
			pszStart = pszBuffer;
			pszEnd = pszStart + nOldLength;

			// loop again to actually do the work
			while (pszStart < pszEnd)
			{
				PXSTR pszTarget;
				while ((pszTarget = (PXSTR) StrTraits::StringFindString(pszStart, pszOld)) != NULL)
				{
					int nBalance = nOldLength - int(pszTarget - pszBuffer + nSourceLen);
					memmove(pszTarget + nReplacementLen, pszTarget + nSourceLen,
							nBalance * sizeof(XCHAR));
					memcpy(pszTarget, pszNew, nReplacementLen * sizeof(XCHAR));
					pszStart = pszTarget + nReplacementLen;
					pszTarget[nReplacementLen + nBalance] = 0;
					nOldLength += (nReplacementLen - nSourceLen);
				}
				pszStart += StrTraits::StringLength(pszStart) + 1;
			}
			BFX_ENSURE(pszBuffer[nNewLength] == 0);
			strResult.SetLength(nNewLength);
		}

		return (strResult);
	}
	int CompareTo(PCXSTR psz, bool bIgnoreCase = false) const
	{
		// NOTE: NULL string allowed.
		// BFX_REQUIRE(psz != NULL);

		PCXSTR pszStr = GetData();
		if (!bIgnoreCase)
		{
			return (StrTraits::StringCompare(pszStr, psz));
		}
		else
		{
			return (StrTraits::StringCompareIgnore(pszStr, psz));
		}
	}
	int IndexOf(XCHAR ch, int iStart = 0) const
	{
		// iStart is in XCHARs
		BFX_REQUIRE(iStart >= 0);

		// nLength is in XCHARs
		int nLength = GetLength();
		if (iStart < 0 || iStart > nLength)
		{
			return (-1);
		}

		PCXSTR pszStr = GetData();

		// find first single character
		PCXSTR psz = StrTraits::StringFindChar(pszStr + iStart, ch);

		// return -1 if not found and index otherwise
		return ((psz == NULL) ? -1 : int(psz - pszStr));
	}
	int IndexOf(PCXSTR pszSub, int iStart = 0) const
	{
		// iStart is in XCHARs
		BFX_REQUIRE(iStart >= 0);
		if (pszSub == NULL)
		{
			return (-1);
		}
		// nLength is in XCHARs
		int nLength = GetLength();
		if (iStart < 0 || iStart > nLength)
		{
			return (-1);
		}
		PCXSTR pszStr = GetData();

		// find first matching substring
		PCXSTR psz = StrTraits::StringFindString(pszStr + iStart, pszSub);

		// return -1 for not found, distance from beginning otherwise
		return ((psz == NULL) ? -1 : int(psz - pszStr));
	}
	int IndexOfAny(PCXSTR pszCharSet, int iStart = 0) const
	{
		// iStart is in XCHARs
		BFX_REQUIRE(iStart >= 0);
		if (pszCharSet == NULL)
		{
			return (-1);
		}
		// nLength is in XCHARs
		int nLength = GetLength();
		if (iStart < 0 || iStart > nLength)
		{
			return (-1);
		}

		PCXSTR psz = GetData();

		PCXSTR pszResult = StrTraits::StringScanSet(psz + iStart, pszCharSet);
		return ((pszResult == NULL) ? -1 : int(pszResult - psz));
	}
	int LastIndexOf(XCHAR ch) const
	{
		PCXSTR psz = GetData();

		// find last single character
		PCXSTR pszResult = StrTraits::StringFindCharRev(psz, ch);

		// return -1 if not found, distance from beginning otherwise
		return (pszResult == NULL) ? -1 : int(pszResult - psz);
	}

	StringT Substring(int iFirst) const
	{
		return Substring(iFirst, GetLength() - iFirst);
	}
	StringT Substring(int iFirst, int nCount) const
	{
		BFX_REQUIRE(iFirst >= 0 && nCount >= 0);
		BFX_REQUIRE((iFirst + nCount) <= GetLength());

		// optimize case of returning entire string
		if (iFirst == 0 && nCount == GetLength())
		{
			return (*this);
		}

		return StringT(GetData() + iFirst, nCount);
	}
	StringT ToUpper() const
	{
		StringT strResult(*this);
		int nLength = strResult.GetLength();

		PXSTR pszBuffer = strResult.GetBuffer(nLength);
		StrTraits::StringUppercase(pszBuffer);
		strResult.SetLength(nLength);

		return strResult;
	}
	StringT ToLower() const
	{
		StringT strResult(*this);
		int nLength = strResult.GetLength();

		PXSTR pszBuffer = strResult.GetBuffer(nLength);
		StrTraits::StringLowercase(pszBuffer);
		strResult.SetLength(nLength);

		return strResult;
	}
	StringT Reverse() const
	{
		StringT strResult(*this);
		int nLength = strResult.GetLength();

		PXSTR pszBuffer = strResult.GetBuffer(nLength);
		StrTraits::StringReverse(pszBuffer);
		strResult.SetLength(nLength);

		return strResult;
	}

	StringT Trim() const
	{
		return (TrimRight().TrimLeft());
	}
	StringT TrimRight() const
	{
		// find beginning of trailing spaces by starting at beginning
		PCXSTR pchStart = GetData();
		PCXSTR pchLast = NULL;
		for (PCXSTR pch = pchStart; *pch != 0; pch++)
		{
			if (StrTraits::IsSpace(*pch))
			{
				if (pchLast == NULL)
					pchLast = pch;
			}
			else
			{
				pchLast = NULL;
			}
		}

		if (pchLast != NULL)
		{
			// truncate at trailing space start
			int iLast = (int) (pchLast - pchStart);

			return Substring(0, iLast);
		}
		return (*this);
	}
	StringT TrimLeft() const
	{
		// find first non-space character
		PCXSTR pchStart = GetData();
		PCXSTR pch = pchStart;

		while (StrTraits::IsSpace(*pch))
		{
			pch++;
		}

		if (pch != pchStart)
		{
			// fixup data and length
			int iFirst = (int) (pch - pchStart);
			int nLength = GetLength() - iFirst;
			return Substring(iFirst, nLength);
		}
		return (*this);
	}
	StringT Trim(XCHAR chTarget) const
	{
		return (TrimRight(chTarget).TrimLeft(chTarget));
	}
	StringT TrimLeft(XCHAR chTarget) const
	{
		// find first non-space character
		PCXSTR pchStart = GetData();
		PCXSTR pch = pchStart;

		while (pch != pchStart)
		{
			pch++;
		}

		if (pch != pchStart)
		{
			// fix-up data and length
			int iFirst = (int) (pch - pchStart);
			int nLength = GetLength() - iFirst;
			return Substring(iFirst, nLength);
		}
		return (*this);
	}
	StringT TrimRight(XCHAR chTarget) const
	{
		// find beginning of trailing matches by starting at beginning
		PCXSTR pchStart = GetData();
		PCXSTR pchLast = NULL;
		for (PCXSTR pch = pchStart; *pch != 0/*NULL*/; pch++)
		{
			if (*pch == chTarget)
			{
				if (pchLast == NULL)
					pchLast = pch;
			}
			else
			{
				pchLast = NULL;
			}
		}

		if (pchLast != NULL)
		{
			// truncate at trailing space start
			int iLast = (int) (pchLast - pchStart);

			return Substring(0, iLast);
		}
		return (*this);
	}
	StringT Trim(PCXSTR pszTargets) const
	{
		return (TrimRight(pszTargets).TrimLeft(pszTargets));
	}
	StringT TrimLeft(PCXSTR pszTargets) const
	{
		// if we're not trimming anything, we're not doing any work
		if ((pszTargets == NULL) || (*pszTargets == 0))
		{
			return (*this);
		}

		PCXSTR pchStart = GetData();
		PCXSTR pch = pchStart;
		while (*pch != 0 && StrTraits::StringFindChar(pszTargets, *pch) != NULL)
		{
			pch++;
		}

		if (pch != pchStart)
		{
			// fix-up data and length
			int iFirst = (int) (pch - pchStart);
			int nLength = GetLength() - iFirst;
			return Substring(iFirst, nLength);
		}
		return (*this);
	}
	StringT TrimRight(PCXSTR pszTargets) const
	{
		// if we're not trimming anything, we're not doing any work
		if ((pszTargets == NULL) || (*pszTargets == 0))
		{
			return (*this);
		}

		// find beginning of trailing matches by starting at beginning
		PCXSTR pchStart = GetData();
		PCXSTR pchLast = NULL;
		for (PCXSTR pch = pchStart; *pch != 0; pch++)
		{
			if (StrTraits::StringFindChar(pszTargets, *pch) != NULL)
			{
				if (pchLast == NULL)
				{
					pchLast = pch;
				}
			}
			else
			{
				pchLast = NULL;
			}
		}

		if (pchLast != NULL)
		{
			// truncate at trailing space start
			int iLast = (int) (pchLast - pchStart);

			return Substring(0, iLast);
		}
		return (*this);
	}

	static StringT __cdecl Format(PCXSTR pszFormat, ...)
	{
		va_list argList;
		StringT strResult;

		va_start(argList, pszFormat);

		int nLength = StrTraits::GetFormattedLength(pszFormat, argList);
		PXSTR pszBuffer = strResult.GetBuffer(nLength);
		StrTraits::Format(pszBuffer, nLength + 1, pszFormat, argList);
		strResult.SetLength(nLength);

		va_end(argList);

		return strResult;
	}

	StringT& operator+=(const StringT& strSrc)
	{
		Append(strSrc, strSrc.GetLength());
		return (*this);
	}
	StringT& operator+=(PCXSTR pszSrc)
	{
		Append(pszSrc);
		return (*this);
	}
	StringT& operator+=(XCHAR chSrc)
	{
		Append(chSrc);
		return (*this);
	}

	friend StringT operator+(const StringT& str1, const StringT& str2)
	{
		StringT strResult(str1);
		strResult += str2;
		return (strResult);
	}
	friend StringT operator+(const StringT& str1, PCXSTR psz2)
	{
		StringT strResult(str1);
		strResult += psz2;
		return (strResult);
	}
	friend StringT operator+(PCXSTR psz1, const StringT& str2)
	{
		StringT strResult(psz1);
		strResult += str2;
		return (strResult);
	}
	friend StringT operator+(const StringT& str1, XCHAR ch2)
	{
		StringT strResult(str1);
		strResult += ch2;
		return (strResult);
	}
	friend StringT operator+(XCHAR ch1, const StringT& str2)
	{
		StringT strResult(ch1);
		strResult += str2;
		return (strResult);
	}
	friend bool operator==(const StringT& str1, const StringT& str2) throw()
	{
		return( str1.CompareTo( str2 ) == 0 );
	}

	friend bool operator==(const StringT& str1, PCXSTR psz2) throw()
	{
		return( str1.CompareTo( psz2 ) == 0 );
	}

	friend bool operator==(PCXSTR psz1, const StringT& str2) throw()
	{
		return( str2.CompareTo( psz1 ) == 0 );
	}

	friend bool operator!=(const StringT& str1, const StringT& str2) throw()
	{
		return( str1.CompareTo( str2 ) != 0 );
	}

	friend bool operator!=(const StringT& str1, PCXSTR psz2) throw()
	{
		return( str1.CompareTo( psz2 ) != 0 );
	}

	friend bool operator!=(PCXSTR psz1, const StringT& str2) throw()
	{
		return( str2.CompareTo( psz1 ) != 0 );
	}

private:
	PXSTR GetBuffer()
	{
		return GetBuffer(GetLength());
	}
	PXSTR GetBuffer(int nLength)
	{
		BFX_ASSERT(nLength >= 0);

		if (m_pData->IsShared())
		{
			// clone it.
			int nOldLength = GetLength();
			int nAllocLength = __MAX(nOldLength, nLength);
			StringData* pNewData = new StringData(nAllocLength);
			if (nOldLength > 0)
			{
				memcpy(pNewData->m_pBuffer, GetData(), nOldLength * sizeof(XCHAR));
				pNewData->m_pBuffer[nOldLength] = 0;
				pNewData->m_nLength = nOldLength;
			}
			m_pData = pNewData;
		}
		else
		{
			// grow it up if necessary.
			m_pData->Capacity(nLength);
		}

		return m_pData->m_pBuffer;
	}
	void SetLength(int nLength)
	{
		BFX_ASSERT(nLength >= 0);
		BFX_ASSERT(nLength <= m_pData->m_nAllocLength);
		BFX_ASSERT(!m_pData->IsShared());

		m_pData->m_nLength = nLength;
		m_pData->m_pBuffer[nLength] = 0;
	}
private:
#ifdef	_MSC_VER
#pragma warning(push)
#pragma warning(disable:4251)
#endif	//	_MSC_VER
	REF<StringData> m_pData;
#ifdef	_MSC_VER
#pragma warning(pop)
#endif	//	_MSC_VER
};

#ifdef	BFX_DLL_BUILD
template class BFX_API StringT<char>;
template class BFX_API StringT<wchar_t>;
#endif	//	_USRDLL

typedef	StringT<char>	String;
typedef	StringT<wchar_t>	StringW;

//////////////////////////////////////////////////////////////////////////////
// special versions of HashTraits for ANSI string.
template<>
class HashTraits<String>
{
public:
	static int __cdecl GetHashCode(const String& key) throw()
	{
		int nHashCode = key.GetLength();
		// use key length to eliminate the range check
		for (int i = 0; i < key.GetLength(); i++)
			nHashCode += (nHashCode << 7 ) ^ key[i];
		// mix it a bit more
		nHashCode -= nHashCode >> 17;
		nHashCode -= nHashCode >> 11;
		nHashCode -= nHashCode >> 5;

		return nHashCode;
	}
	static bool __cdecl Equals(const String& key1, const String& key2) throw()
	{
		return key1 == key2;
	}
};

// special versions of HashTraits for UNICODE string.
template<>
class HashTraits<StringW>
{
public:
	static int __cdecl GetHashCode(const StringW& key) throw()
	{
		int nHashCode = key.GetLength();
		// use key length to eliminate the rangecheck
		for (int i = 0; i < key.GetLength(); i++)
			nHashCode += (nHashCode << 7 ) ^ key[i];
		// mix it a bit more
		nHashCode -= nHashCode >> 17;
		nHashCode -= nHashCode >> 11;
		nHashCode -= nHashCode >> 5;

		return nHashCode;
	}
	static bool __cdecl Equals(const StringW& key1, const StringW& key2) throw()
	{
		return key1 == key2;
	}
};

} /* namespace BFX */

#endif /* __BFX_STRING_H__ */
